﻿#define _CRT_SECURE_NO_WARNINGS 1

//最大公约数
//最大公约数是指两个或多个整数共有约数中最大的⼀个。
// 题目描述：
//输入2个整数m和n，计算m和n的最大公约数，并打印出结果。

#include<stdio.h>

int gcd(int m, int n)
{
	if (n == 0)
		return m;
	else
		return gcd(n, m % n);
}

int main()
{
	int num1 = 0;
	int num2 = 0;
	int i = 0;

	//第一种方法，试除法
	scanf("%d %d", &num1, &num2);
	//从二者中的最小值开始相除
	for (i = (num1 > num2 ? num2 : num1); i > 0; i--)
	{
		////每次拿i试除，如果不能同时整除，则i--，继续试除
		if (num1 % i == 0 && num2 % i == 0)
		{
			//整除就打印公约数并跳出循环
			printf("最大公约数：%d\n", i);
			break;
		}
	}

	//第二种方法：辗转相除法
	/*	辗转相除法也称为欧⼏⾥得算法，是⼀种⽤来求两个正整数最⼤公约数的⽅法。它基于⼀个简单的
		数学原理：如果 a 和 b 是两个正整数，且 a > b ，则a和b的最大公约数等于 b 和 a% b
		（ a除以b所得的余数）的最大公约数
	*/
	//假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
		//	1997 ÷ 615 = 3 (余 152)
		//	615 ÷ 152 = 4(余7)
		//	152 ÷ 7 = 21(余5)
		//	7 ÷ 5 = 1 (余2)
		//	5 ÷ 2 = 2 (余1)
		//	2 ÷ 1 = 2 (余0)
		//	至此，最大公约数为1
	//被除数和除数在每次计算后调换，让被除数等于除数，让除数等于余数，如果余数为0，那么这个除数就是最大公约数

	int m = 0;
	int n = 0;
	int r = 0;

	scanf("%d %d", &m, &n);



	while (r = m % n)//当r==0时,说明找到公约数，不执行循环
	{
		m = n;//以除数作为被除数
		n = r;//以余数作为除数
	}

	printf("最大公约数:%d\n", n);

	//递归的辗转相除法
	//因为这个欧几里得算法它的除数和被除数嵌套，有点递推的思路
	//尝试用递归解决
	int ret = gcd(m, n);
	//ret 来接收返回值

	printf("最大公约数:%d", ret);

	return 0;
}


